package com.aqie.medium.doubleDimensionalArray;

/**
 * 289
 * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
 * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
 * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
 * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
 *
 */
public class GameOfLife {
    /**
     * 1.位运算
     * 原地更新就是在原数组更新， 二进制10表示由0变成1，即10进制2 二进制11 表示由1变成1 ，即10进制3
     * 二进制01表示由1变成0，即10进制1 最后只要输出左边的1位即可，
     * 可以用位运算>>1加快效率, & 1表示取最右边1位
     * @param board
     */
    public void gameOfLife(int[][] board) {
        int R = board.length;
        if (R == 0) return;
        int C = board[0].length;

        int newX, newY, live;
        //         左上 上 右上  右 右下 下 左下 左
        int dx[] = {-1,-1,-1, 0, 1, 1,  1, 0 };
        int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

        for (int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                live = 0;
                for (int k = 0; k < 8; k++){
                    newX = i + dx[k];
                    newY = j + dy[k];
                    if (newX >= 0 && newX < R && newY >= 0 && newY < C){
                        if ((board[newX][newY] & 1) > 0) live++;
                    }
                }
                if ((board[i][j] & 1) > 0 && (live < 2)) board[i][j] = 1;
                if ((board[i][j] & 1) > 0 && (live == 2 || live == 3 )) board[i][j] = 3;
                if ((board[i][j] & 1) > 0 && live > 3) board[i][j] = 1;
                if (!((board[i][j] & 1) > 0) && live == 3 ) board[i][j] = 2;
            }
        }

        for (int i=0; i<R; i++)
            for (int j=0; j<C; j++)
                board[i][j] = board[i][j] >> 1;

    }

    /**
     * 一个优化是用2代表新的（由死细胞转化的）活细胞，3代表（由活细胞转化的）死细胞。这样在遍历时可以用%2（&1）
     */
    public void gameOfLife2(int[][] board) {
        int count;
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                count = 0;
                if (i - 1 >= 0 && board[i - 1][j] % 2 != 0) count++;
                if (i - 1 >= 0 && j - 1 >= 0 && board[i - 1][j - 1] % 2 != 0) count++;
                if (j - 1 >= 0 && board[i][j - 1] % 2 != 0) count++;
                if (i - 1 >= 0 && j + 1 < board[0].length && board[i - 1][j + 1] % 2 != 0) count++;
                if (j + 1 < board[0].length && board[i][j + 1] != 0) count++;
                if (i + 1 < board.length && j + 1 < board[0].length && board[i + 1][j + 1] != 0) count++;
                if (i + 1 < board.length && board[i + 1][j] != 0) count++;
                if (i + 1 < board.length && j - 1 >= 0 && board[i + 1][j - 1] != 0) count++;
                if (board[i][j] == 1 && (count < 2 || count > 3)) board[i][j] = 3;
                else if (board[i][j] == 0 && count == 3) board[i][j] = 2;
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 2) board[i][j] = 1;
                else if (board[i][j] == 3) board[i][j] = 0;
            }
        }
    }
}
